package complexity;

public class Quick {
    public static void sort(Comparable[] comparable) {
        int lo = 0;
        int high = comparable.length - 1;
        sort(comparable, lo, high);
    }

    public static void sort(Comparable[] comparable, int low, int high) {
        if (low >= high) {
            return;
        }
        //分为两组分别为左子组和右子组
        int mid = partition(comparable, low, high);
        //让左子组有序
        sort(comparable, low, mid - 1);
        //让右子组有序
        sort(comparable, mid + 1, high);

    }

    public static int partition(Comparable[] comparable, int low, int high) {
        /**
         * 1,找个基准值，分别用两个指针分别指向数组的头部和尾部；
         * 2,先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
         * 3,再头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针位置；
         * 4,交换当前左边指针位置和右边指针位置的元素
         * 5,重复2，3，4不走，知道左边指针的值大于右边指针的值停止
         */
        //分解值元素
        Comparable com = comparable[low];
        int left = low;
        int right = high + 1;
        while (true) {
            while (com.compareTo(comparable[--right])<0) {
                if (right == low) {
                    break;
                }
            }
            while (com.compareTo(comparable[++left])>0) {
                if (left== high) {
                    break;
                }
            }
            if (left >= right) {
                break;
            } else {
                Bubble.exChange(comparable, left, right);
            }
        }
        Bubble.exChange(comparable,low,right);
        return right;
    }

    public static boolean lower(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
}
